Следствие о числе ребер планарного графа

Если **обыкновенный** связный планарный граф $G$ содержит $n$ вершин и $m$ ребер и $n \geq 3$, то $m \leq 3n - 6$.

Пусть $(G, \Gamma)$ — плоский граф. Положим $r = r(G)$. Можно считать, что $G$ не является путем длины 2 (для него неравенство выполнено). Длиной границы грани назовем число ребер в этой границе. Пусть $t(\Gamma)$ — сумма длин границ всех граней изображения $\Gamma$. Граница грани не может состоять менее чем из трех ребер, следовательно $t(\Gamma) \geq 3r$. По лемме о числе границ при подсчете $t(\Gamma)$ каждое ребро учтено не более чем дважды, следовательно $t(\Gamma) \leq 2m$. Отсюда получаем, что $3r \leq 2m$. По тождеству Эйлера $r = m - n + 2$, тогда $$3(m - n + 2) \leq 2m \Rightarrow 3m - 3n + 6 \leq 2m \Rightarrow m \leq 3n - 6$$ $\square$

Полный граф $K_5$ не планарен.

Граф $K_5$ содержит 5 вершин и 10 ребер. Так как $10 \not\leq 3 \cdot 5 - 6$, то по следствию о числе ребер для планарного графа, $K_5$ не планарен. $\square$

Полный двудольный граф $K_{3,3}$ не планарен.

Докажем от противного. Пусть граф $K_{3,3}$ планарен, и $\Gamma$ — его правильное изображение на плоскости. В графе $K_{3,3}$ 6 вершин и 9 ребер, тогда по тождеству Эйлера число граней равно $f = m - n + 2 = 9 - 6 + 2 = 5$. По критерию двудольности граф $K_{3,3}$ не содержит треугольников, следовательно, каждая грань в $\Gamma$ ограничена как минимум 4 ребрами. Сумма длин границ всех граней $t(\Gamma)$ должна быть не меньше $4f = 4 \cdot 5 = 20$. С другой стороны, по лемме о числе границ, $t(\Gamma)$ в точности равно удвоенному числу ребер: $$t(\Gamma) = 2m = 2 \cdot 9 = 18$$ Получаем противоречие: $20 \leq t(\Gamma) = 18$. Следовательно, граф $K_{3,3}$ не планарен. $\square$